/* 树（Tree）练习题参考答案（C语言实现）*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <string.h>

// 二叉树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// ======================= 基础题解答 =======================

// 1. 计算二叉树的节点个数
int countNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// 2. 计算叶子节点个数
int countLeafNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

// 3. 计算树的高度
int getHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 4. 检查两棵树是否相同
bool isSameTree(TreeNode* p, TreeNode* q) {
    // 如果两个节点都为空，则相同
    if (p == NULL && q == NULL) {
        return true;
    }
    // 如果只有一个节点为空，则不同
    if (p == NULL || q == NULL) {
        return false;
    }
    // 检查当前节点的值是否相同，以及左右子树是否相同
    return (p->data == q->data) && 
           isSameTree(p->left, q->left) && 
           isSameTree(p->right, q->right);
}

// 辅助函数：检查两个子树是否镜像对称
bool isMirror(TreeNode* left, TreeNode* right) {
    if (left == NULL && right == NULL) {
        return true;
    }
    if (left == NULL || right == NULL) {
        return false;
    }
    return (left->data == right->data) && 
           isMirror(left->left, right->right) && 
           isMirror(left->right, right->left);
}

// 5. 检查二叉树是否对称
bool isSymmetric(TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    return isMirror(root->left, root->right);
}

// 6. 翻转二叉树
TreeNode* invertTree(TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    // 交换左右子树
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    
    // 递归翻转左右子树
    invertTree(root->left);
    invertTree(root->right);
    
    return root;
}

// ======================= 提高题解答 =======================

// 7. 二叉树的最大深度
int maxDepth(TreeNode* root) {
    return getHeight(root); // 复用之前的getHeight函数
}

// 8. 二叉树的最小深度
int minDepth(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    // 如果是叶子节点
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    
    // 如果左子树为空，计算右子树的最小深度
    if (root->left == NULL) {
        return minDepth(root->right) + 1;
    }
    
    // 如果右子树为空，计算左子树的最小深度
    if (root->right == NULL) {
        return minDepth(root->left) + 1;
    }
    
    // 左右子树都不为空，取较小值
    int leftDepth = minDepth(root->left);
    int rightDepth = minDepth(root->right);
    return (leftDepth < rightDepth ? leftDepth : rightDepth) + 1;
}

// 辅助队列用于层序遍历
typedef struct {
    TreeNode* nodes[1000]; // 假设最多1000个节点
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
}

void enqueue(Queue* q, TreeNode* node) {
    q->nodes[q->rear++] = node;
}

TreeNode* dequeue(Queue* q) {
    return q->nodes[q->front++];
}

bool isQueueEmpty(Queue* q) {
    return q->front == q->rear;
}

// 9. 二叉树的层序遍历（返回结果数组，简化实现）
void levelOrderTraversal(TreeNode* root, int*** result, int* returnSize, int** returnColumnSizes) {
    if (root == NULL) {
        *returnSize = 0;
        return;
    }
    
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    
    // 预分配结果空间
    *result = (int**)malloc(sizeof(int*) * 100); // 假设最多100层
    *returnColumnSizes = (int*)malloc(sizeof(int) * 100);
    *returnSize = 0;
    
    while (!isQueueEmpty(&q)) {
        int levelSize = q.rear - q.front;
        int* levelValues = (int*)malloc(sizeof(int) * levelSize);
        
        // 处理当前层的所有节点
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = dequeue(&q);
            levelValues[i] = node->data;
            
            if (node->left != NULL) {
                enqueue(&q, node->left);
            }
            if (node->right != NULL) {
                enqueue(&q, node->right);
            }
        }
        
        // 保存当前层的结果
        (*result)[*returnSize] = levelValues;
        (*returnColumnSizes)[*returnSize] = levelSize;
        (*returnSize)++;
    }
}

// 辅助函数：验证二叉搜索树（使用上下界）
bool isValidBSTHelper(TreeNode* root, long long lower, long long upper) {
    if (root == NULL) {
        return true;
    }
    
    if (root->data <= lower || root->data >= upper) {
        return false;
    }
    
    return isValidBSTHelper(root->left, lower, root->data) && 
           isValidBSTHelper(root->right, root->data, upper);
}

// 10. 二叉搜索树的验证
bool isValidBST(TreeNode* root) {
    return isValidBSTHelper(root, LLONG_MIN, LLONG_MAX);
}

// 11. 寻找二叉搜索树的最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL) {
        return NULL;
    }
    
    // 如果p和q都小于当前节点，在左子树中查找
    if (p->data < root->data && q->data < root->data) {
        return lowestCommonAncestor(root->left, p, q);
    }
    
    // 如果p和q都大于当前节点，在右子树中查找
    if (p->data > root->data && q->data > root->data) {
        return lowestCommonAncestor(root->right, p, q);
    }
    
    // 如果p和q分别在当前节点的两侧，或者其中一个就是当前节点，那么当前节点就是最近公共祖先
    return root;
}

// 辅助函数：计算二叉树的直径
int diameterOfBinaryTreeHelper(TreeNode* root, int* diameter) {
    if (root == NULL) {
        return 0;
    }
    
    int leftHeight = diameterOfBinaryTreeHelper(root->left, diameter);
    int rightHeight = diameterOfBinaryTreeHelper(root->right, diameter);
    
    // 更新直径
    *diameter = (*diameter > leftHeight + rightHeight) ? *diameter : (leftHeight + rightHeight);
    
    // 返回当前子树的高度
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 12. 二叉树的直径
int diameterOfBinaryTree(TreeNode* root) {
    int diameter = 0;
    diameterOfBinaryTreeHelper(root, &diameter);
    return diameter;
}

// 13. 路径总和
bool hasPathSum(TreeNode* root, int targetSum) {
    if (root == NULL) {
        return false;
    }
    
    // 如果是叶子节点，检查剩余值是否等于节点值
    if (root->left == NULL && root->right == NULL) {
        return root->data == targetSum;
    }
    
    // 递归检查左右子树
    int remainingSum = targetSum - root->data;
    return hasPathSum(root->left, remainingSum) || hasPathSum(root->right, remainingSum);
}

// ======================= 挑战题解答 =======================

// 辅助函数：计算二叉树中的最大路径和
int maxPathSumHelper(TreeNode* root, int* maxSum) {
    if (root == NULL) {
        return 0;
    }
    
    // 计算左右子树的最大路径和（如果为负则取0）
    int leftSum = maxPathSumHelper(root->left, maxSum);
    int rightSum = maxPathSumHelper(root->right, maxSum);
    leftSum = (leftSum > 0) ? leftSum : 0;
    rightSum = (rightSum > 0) ? rightSum : 0;
    
    // 更新全局最大路径和
    int currentSum = root->data + leftSum + rightSum;
    if (currentSum > *maxSum) {
        *maxSum = currentSum;
    }
    
    // 返回包含当前节点的最大路径和（只能选择左或右子树中的一条路径）
    return root->data + ((leftSum > rightSum) ? leftSum : rightSum);
}

// 14. 二叉树中的最大路径和
int maxPathSum(TreeNode* root) {
    int maxSum = INT_MIN;
    maxPathSumHelper(root, &maxSum);
    return maxSum;
}

// 辅助函数：在中序遍历数组中查找值的索引
int findIndex(int* arr, int start, int end, int val) {
    for (int i = start; i <= end; i++) {
        if (arr[i] == val) {
            return i;
        }
    }
    return -1; // 找不到
}

// 15. 根据前序遍历和中序遍历重建二叉树
TreeNode* buildTreeHelper(int* preorder, int preStart, int preEnd, 
                         int* inorder, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
        return NULL;
    }
    
    // 前序遍历的第一个元素是根节点
    int rootVal = preorder[preStart];
    TreeNode* root = createNode(rootVal);
    
    // 找到根节点在中序遍历中的位置
    int rootIndex = findIndex(inorder, inStart, inEnd, rootVal);
    
    // 计算左子树节点数量
    int leftSize = rootIndex - inStart;
    
    // 递归构建左右子树
    root->left = buildTreeHelper(preorder, preStart + 1, preStart + leftSize, 
                                inorder, inStart, rootIndex - 1);
    root->right = buildTreeHelper(preorder, preStart + leftSize + 1, preEnd, 
                                 inorder, rootIndex + 1, inEnd);
    
    return root;
}

TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    return buildTreeHelper(preorder, 0, preorderSize - 1, 
                          inorder, 0, inorderSize - 1);
}

// 辅助函数：序列化二叉树（使用前序遍历）
void serializeHelper(TreeNode* root, char* str, int* index) {
    if (root == NULL) {
        strcpy(str + *index, "null,");
        *index += 5;
        return;
    }
    
    // 将当前节点的值转换为字符串
    sprintf(str + *index, "%d,", root->data);
    
    // 移动索引到下一个位置
    while (str[*index] != ',') {
        (*index)++;
    }
    (*index)++;
    
    // 递归序列化左右子树
    serializeHelper(root->left, str, index);
    serializeHelper(root->right, str, index);
}

// 16. 序列化二叉树
char* serialize(TreeNode* root) {
    // 假设每个节点最多占用10个字符，包括分隔符
    char* str = (char*)malloc(sizeof(char) * 10000);
    int index = 0;
    serializeHelper(root, str, &index);
    str[index - 1] = '\0'; // 移除最后的逗号
    return str;
}

// 辅助函数：反序列化二叉树
TreeNode* deserializeHelper(char** str) {
    // 跳过空格
    while (**str == ' ') {
        (*str)++;
    }
    
    // 检查是否为null
    if (**str == 'n') {
        *str += 4; // 跳过"null"
        if (**str == ',') {
            (*str)++;
        }
        return NULL;
    }
    
    // 解析数字
    int val = 0;
    int sign = 1;
    if (**str == '-') {
        sign = -1;
        (*str)++;
    }
    while (isdigit(**str)) {
        val = val * 10 + (**str - '0');
        (*str)++;
    }
    val *= sign;
    
    // 跳过逗号
    if (**str == ',') {
        (*str)++;
    }
    
    // 创建节点并递归反序列化左右子树
    TreeNode* node = createNode(val);
    node->left = deserializeHelper(str);
    node->right = deserializeHelper(str);
    
    return node;
}

// 16. 反序列化二叉树
TreeNode* deserialize(char* data) {
    return deserializeHelper(&data);
}

// 辅助函数：打家劫舍III（动态规划）
void robHelper(TreeNode* root, int* robResult, int* notRobResult) {
    if (root == NULL) {
        *robResult = 0;
        *notRobResult = 0;
        return;
    }
    
    int leftRob, leftNotRob, rightRob, rightNotRob;
    robHelper(root->left, &leftRob, &leftNotRob);
    robHelper(root->right, &rightRob, &rightNotRob);
    
    // 如果当前节点被打劫，子节点不能被打劫
    *robResult = root->data + leftNotRob + rightNotRob;
    
    // 如果当前节点不被打劫，子节点可以选择打劫或不打劫，取较大值
    *notRobResult = ((leftRob > leftNotRob) ? leftRob : leftNotRob) + 
                    ((rightRob > rightNotRob) ? rightRob : rightNotRob);
}

// 17. 打家劫舍III
int rob(TreeNode* root) {
    int robResult, notRobResult;
    robHelper(root, &robResult, &notRobResult);
    return (robResult > notRobResult) ? robResult : notRobResult;
}

// 18. 合并二叉树
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (root1 == NULL) {
        return root2;
    }
    if (root2 == NULL) {
        return root1;
    }
    
    // 合并当前节点
    root1->data += root2->data;
    
    // 递归合并左右子树
    root1->left = mergeTrees(root1->left, root2->left);
    root1->right = mergeTrees(root1->right, root2->right);
    
    // 释放root2的内存（可选）
    free(root2);
    
    return root1;
}

// 19. 二叉树中的下一个节点（假设中序遍历）
// 这里简化实现：先找到目标节点，然后找到其中序后继
TreeNode* findNode(TreeNode* root, int val) {
    if (root == NULL || root->data == val) {
        return root;
    }
    
    TreeNode* left = findNode(root->left, val);
    if (left != NULL) {
        return left;
    }
    return findNode(root->right, val);
}

TreeNode* findMin(TreeNode* root) {
    TreeNode* current = root;
    while (current && current->left != NULL) {
        current = current->left;
    }
    return current;
}

TreeNode* findSuccessorHelper(TreeNode* root, TreeNode* target, TreeNode* successor) {
    if (root == NULL) {
        return successor;
    }
    
    if (root->data > target->data) {
        // 当前节点可能是后继，继续在左子树中查找
        return findSuccessorHelper(root->left, target, root);
    } else {
        // 后继在右子树中
        return findSuccessorHelper(root->right, target, successor);
    }
}

TreeNode* getInorderSuccessor(TreeNode* root, int val) {
    TreeNode* target = findNode(root, val);
    if (target == NULL) {
        return NULL;
    }
    
    // 如果有右子树，则右子树中的最小值就是后继
    if (target->right != NULL) {
        return findMin(target->right);
    }
    
    // 否则，从根节点开始向上查找
    return findSuccessorHelper(root, target, NULL);
}

// 辅助函数：释放树的内存
void freeTree(TreeNode* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

// 打印二叉树的辅助函数（前序遍历）
void printTree(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        printTree(root->left);
        printTree(root->right);
    }
}

// 示例：创建一个测试树
TreeNode* createTestTree() {
    /* 创建如下树：
        3
       / \
      9  20
        /  \
       15   7
    */
    TreeNode* root = createNode(3);
    root->left = createNode(9);
    root->right = createNode(20);
    root->right->left = createNode(15);
    root->right->right = createNode(7);
    return root;
}

// 主函数：测试部分功能
int main() {
    TreeNode* root = createTestTree();
    
    printf("===== 测试基础题 =====\n");
    printf("节点个数: %d\n", countNodes(root));
    printf("叶子节点个数: %d\n", countLeafNodes(root));
    printf("树的高度: %d\n", getHeight(root));
    printf("树是否对称: %s\n", isSymmetric(root) ? "是" : "否");
    
    printf("\n===== 测试翻转二叉树 =====\n");
    printf("原树（前序）: ");
    printTree(root);
    printf("\n");
    TreeNode* inverted = invertTree(root);
    printf("翻转后（前序）: ");
    printTree(inverted);
    printf("\n");
    
    // 重新创建测试树
    freeTree(inverted);
    root = createTestTree();
    
    printf("\n===== 测试提高题 =====\n");
    printf("最大深度: %d\n", maxDepth(root));
    printf("最小深度: %d\n", minDepth(root));
    
    // 测试路径总和
    printf("路径总和为30: %s\n", hasPathSum(root, 30) ? "存在" : "不存在");
    printf("路径总和为28: %s\n", hasPathSum(root, 28) ? "存在" : "不存在");
    
    // 测试最大路径和
    printf("最大路径和: %d\n", maxPathSum(root));
    
    // 释放内存
    freeTree(root);
    
    // 测试根据前序和中序构建树
    printf("\n===== 测试重建二叉树 =====\n");
    int preorder[] = {3, 9, 20, 15, 7};
    int inorder[] = {9, 3, 15, 20, 7};
    TreeNode* builtTree = buildTree(preorder, 5, inorder, 5);
    printf("重建的树（前序）: ");
    printTree(builtTree);
    printf("\n");
    
    // 释放内存
    freeTree(builtTree);
    
    printf("\n测试完成！\n");
    return 0;
}

/*
## 代码说明

### 数据结构定义
- 使用标准的二叉树节点结构 `TreeNode`
- 定义了辅助队列 `Queue` 用于层序遍历操作

### 基础题实现
1. **节点计数**：递归计算左右子树节点数之和加1
2. **叶子节点计数**：递归计算，判断节点是否没有子节点
3. **树的高度**：递归计算左右子树高度的最大值加1
4. **树的相同性**：递归比较对应节点的值和结构
5. **对称性检查**：使用辅助函数检查是否为镜像结构
6. **翻转二叉树**：递归交换左右子树

### 提高题实现
7. **最大深度**：复用树高度计算函数
8. **最小深度**：递归计算，注意处理只有一个子树的情况
9. **层序遍历**：使用队列实现，按层返回结果
10. **二叉搜索树验证**：使用上下界递归检查
11. **最近公共祖先**：利用二叉搜索树的性质递归查找
12. **二叉树直径**：计算每个节点左右子树高度之和的最大值
13. **路径总和**：递归减去过路节点的值，检查是否存在符合条件的路径

### 挑战题实现
14. **最大路径和**：使用辅助函数跟踪全局最大值和单侧路径和
15. **重建二叉树**：利用前序和中序遍历的特性递归构建
16. **序列化与反序列化**：使用前序遍历实现
17. **打家劫舍III**：动态规划，返回选和不选当前节点的最大值
18. **合并二叉树**：递归合并对应节点
19. **下一个节点**：找到中序遍历的后继节点

### 使用提示

1. 代码中的实现主要关注算法逻辑，可能需要根据具体环境进行调整
2. 内存管理：示例中已包含释放树内存的函数，但实际使用时需注意避免内存泄漏
3. 挑战题中的某些实现进行了简化，完整实现可能需要更复杂的代码
4. 对于第20题（不同的二叉搜索树II），由于实现较复杂且返回结果为树的集合，代码中未包含

### 测试

主函数中包含了部分功能的测试代码，创建了一个示例树并测试了几个关键函数。可以根据需要扩展测试用例或添加其他功能的测试。

通过完成这些练习题和理解相应的实现，你将能够更深入地掌握树数据结构的概念和应用。*/